<!DOCTYPE html>
<html lang="en">
<head>
	<meta charset="UTF-8">
	<meta http-equiv="X-UA-Compatible" content="IE=edge">
	<meta name="viewport" content="width=device-width, initial-scale=1.0">
	<title>Document</title>
</head>
<body>
	<script>

		// 插入排序
		function insertSort(arr) {
			const { length } = arr
			let temp
			for(let i = 0; i< length; i++) {
				temp = arr[i]
				let j = i
				while(j > 0 && arr[j-1] > temp) {
					arr[j] = arr[j-1]
					j--
				}
				arr[j] = temp
			}
			// console.log(arr);
			return arr
		}
		// insertSort([5,4,3,2,1,6,8])

		function bucketSort(arr, bucketSize = 3) {
			if (arr.length < 2) {
				return arr
			}
			// 创建几个小桶, 按小桶分好
			const buckets = createBucket(arr, bucketSize)

			// 小桶排序(插入排序算法), 合并 concat
			return sortBuckets(buckets)
		}
		
		function createBucket(arr, bucketSize) {
			let minValue = Math.min(...arr)
			let maxValue = Math.max(...arr)

			const bucetCount = Math.floor((maxValue - minValue) / bucketSize) + 1
			const buckets = [...Array(bucetCount)].map(() => [])
			for (let i = 0; i < arr.length; i++) {
				const index = Math.floor((arr[i] - minValue) / bucketSize)
				buckets[index].push(arr[i]) // 放到对应的桶,前一个桶的值必定比后一个桶小
			}
			console.log(36, buckets)
			return buckets
		}

		function sortBuckets(arr) {
			let sortArr = []
			for(let i = 0; i < arr.length; i++) {
				if (arr[i]) {
					insertSort(arr[i]) // 把小桶内的值再进行排序
					console.log(arr[i]);
					sortArr = sortArr.concat(...arr[i])
				}
			}
			console.log('sortArr', sortArr);
			return sortArr
		}
		bucketSort([5,4,3,2,6,1,7,10,9,8])



	</script>
</body>
</html>